#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 
# Copyright (c) 2017 Baidu.com, Inc. All Rights Reserved
# 

"""
File: run13.py
Author: zhangyang(zhangyang40@baidu.com)
Date: 2018/1/5 0005 14:13
"""
"""
输入两棵二叉树A，B，判断B是不是A的子结构。
ps：我们约定空树不是任意一个树的子结构
"""


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def isSubtree(self, pRootA, pRootB):
        if pRootB is None: return True
        if pRootA is None: return False
        if pRootA.val == pRootB.val:
            return self.isSubtree(pRootA.left, pRootB.left) and self.isSubtree(pRootA.right, pRootB.right)
        else:
            return False

    def HasSubtree(self, pRootA, pRootB):
        if pRootA is None and pRootB is None: return False
        return self.isSubtree(pRootA, pRootB) and self.HasSubtree(pRootA.left, pRootB) and self.HasSubtree(pRootA.right,
                                                                                                           pRootB)
